//将两个有序顺序表合并为一 个新的有序顺序表， 并由西数返回结果顺序表。
#include<iostream>
using namespace std;
#define MaxSize 50
#define ElemType int

struct List{
    ElemType data[MaxSize];
    int length;

    int InitList(List &L){
        L.length=0;
        return L.length;
    }

    int Length(List &L){
        return L.length;
    }

    bool ListInsert(List &L,int i,ElemType e){
        if(i<1||i>L.length+1){   //判断i的范围是否有效
            return false;
        }
        if(L.length>=MaxSize){   //当前存储空间已满，不能插入
            return false;
        }
        for (int j = L.length; j >= i; j--){ //将第i个元素及之后的元素后移
            L.data[j]=L.data[j-1];
        }
        L.data[i-1]=e;           //在第i个位置放入e
        L.length++;              //线性表长度加1
        return true;
        
    }
};

ElemType* merge2SequentialList(List &l1,List &l2){
    //使用双指针
    int i=0,j=0,k=0;
    ElemType* list = new ElemType[l1.length+l2.length];
    while ( i < l1.length && j<l2.length)
    {
        if(l1.data[i]<=l2.data[j]){
            list[k]=l1.data[i];
            i++;
            k++;
        }else{
            list[k]=l2.data[j];
            j++;
            k++;
        }
    }
    while (i<l1.length){
        list[k]=l1.data[i];
        k++;
        i++;
    }
    while (j<l2.length){
        list[k]=l2.data[j];
        k++;
        j++;
    }

    return list;
}


int main(){
    List l;
    l.InitList(l);
    // l.ListInsert(l,1,1);
    // l.ListInsert(l,2,2);
    // l.ListInsert(l,3,2);
    // l.ListInsert(l,4,3);
    // l.ListInsert(l,5,4);
    // l.ListInsert(l,6,3);
    l.ListInsert(l,1,1);
    l.ListInsert(l,2,1);
    l.ListInsert(l,3,1);
    l.ListInsert(l,4,1);
    l.ListInsert(l,5,1);
    l.ListInsert(l,6,1);

    List l2;
    l2.InitList(l2);
    // l.ListInsert(l,1,1);
    // l.ListInsert(l,2,2);
    // l.ListInsert(l,3,2);
    // l.ListInsert(l,4,3);
    // l.ListInsert(l,5,4);
    // l.ListInsert(l,6,3);
    l2.ListInsert(l2,1,2);
    l2.ListInsert(l2,2,3);
    l2.ListInsert(l2,3,4);
    l2.ListInsert(l2,4,5);
    l2.ListInsert(l2,5,6);
    l2.ListInsert(l2,6,7);

    ElemType* arr =  merge2SequentialList(l,l2);
            cout<<sizeof(arr)<<endl;
                        cout<<typeid(arr).name()<<endl;

    for (int  i = 0; i < 12; i++)
    {
        cout<<arr[i]<<endl;
    }
    
    return 0;
}